What's a Binary Search Tree? a binary tree carefully constructed for fast lookup of items What operations does a Binary Search Tree provide? add an item find an item remove an item For these operations, how do Binary Search Trees compare to Lists? Lists are O(n) BSTs are O(log n) (BSTs don't provide indexed access to items) In the average case, how many steps are needed to find an item in a List of 1,000,000 items? 500,000 In the average case, how many steps are needed to find an item in a Binary Search Tree of 1,000,000 items? 20 What other data types are efficiently implemented using Binary Search Trees? Set Map Priority Queue What's a Key? part of an item used for searching What's the defining property of a Binary Search Tree? BST Order Property for every node X in the tree keys in left subtree are smaller than key in X keys in right subtree are larger than key in X Draw an example BST on the board. How do you find a key in a Binary Search Tree? compare x to root if smaller, repeat in left subtree if larger, repeat in right subtree Show the steps of finding a key in a BST on the board. How do you find the minimum key in a Binary Search Tree? repeatedly follow left child How do you find the maximum key in a Binary Search Tree? repeatedly follow right child How do you insert a key in a Binary Search Tree? in place of null pointer where find failed Show the steps of inserting a key in a BST on the board. How do you remove a key from a Binary Search Tree? find node to remove How do you remove a leaf node from a Binary Search Tree? if leaf, remove node How do you remove a one-child node from a Binary Search Tree? if one child, connect parent to child Show the steps of removing a one-child node from a BST on the board. How do you remove a two-child node from a Binary Search Tree? replace with smallest node in right subtree remove smallest node in right subtree Show the steps of removing a two-child node from a BST on the board. Classwork You may work with a partner. Show the result of inserting C, A, D, F, E, B into an initially empty BST. Show the result of removing C, E, D from the previous BST. Write the code for find, insert, and remove on a BST. How do child pointers get set correctly during insert and remove?